|
Pointer jumping or path doubling is a design technique for parallel algorithms that operate on pointer structures, such as linked lists and directed graphs. It can be used to find the roots of a forest of rooted trees, and can also be applied to parallelize many other graph algorithms including connected components, minimum spanning trees, and biconnected components. == List ranking == One of the simpler tasks that can be solved by a pointer jumping algorithm is the ''list ranking'' problem. This problem is defined as follows: given a linked list of nodes, find the distance (measured in the number of nodes) of each node to the end of the list. The distance is defined as follows, for nodes that point to their successor by a pointer called : * If is , then . * For any other node, . This problem can easily be solved in linear time on a sequential machine, but a parallel algorithm can do better: given processors, the problem can be solved in logarithmic time, , by the following pointer jumping algorithm: * Allocate an array of integers. * Initialize: for each processor/list node , in parallel: * * If , set . * * Else, set . * While any node has : * * For each processor/list node , in parallel: * * * If : * * * * Set . * * * * Set . The pointer jumping occurs in the last line of the algorithm, where each node's pointer is reset to skip the node's direct successor. It is assumed, as in common in the PRAM model of computation, that memory access are performed in lock-step, so that each memory fetch is performed before each memory store; otherwise, processors may clobber each other's data, producing inconsistencies. Analyzing the algorithm yields a logarithmic running time. The initialization loop takes constant time, because each of the processors performs a constant amount of work, all in parallel. The inner loop of the main loop also takes constant time, as does (by assumption) the termination check for the loop, so the running time is determined by how often this inner loop is executed. Since the pointer jumping in each iteration splits the list into two parts, one consisting of the "odd" elements and one of the "even" elements, the length of the list pointed to by each processor's is halved in each iteration, which can be done at most time before each list has a length of at most one. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pointer jumping」の詳細全文を読む スポンサード リンク
|